package code.oldCode.classic150;

import utils.TreeNode;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/20
 */
public class Classic150_binaryTree {

    /* 104. 二叉树的最大深度 */
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    /* 100. 相同的树 */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        if (p.val != q.val)
            return false;

        boolean isSameLeft = isSameTree(p.left, q.left);
        boolean isSameRight = isSameTree(p.right, q.right);

        return isSameLeft && isSameRight;
    }

    /* 226. 翻转二叉树 */
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    /* 101. 对称二叉树 */
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;
        return compareSymmetric(leftNode, rightNode);
    }

    private boolean compareSymmetric(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null)
            return true;
        if (leftNode == null || rightNode == null)
            return false;
        if (leftNode.val != rightNode.val)
            return false;
        boolean isSymmetric1 = compareSymmetric(leftNode.left, rightNode.right);
        boolean isSymmetric2 = compareSymmetric(leftNode.right, rightNode.left);
        return isSymmetric1 && isSymmetric2;
    }

    /* 105. 从前序与中序遍历序列构造二叉树 */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
        int len = preorder.length;
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, inorderMap, 0, len - 1, 0, len - 1);
    }

    private TreeNode build(int[] preorder, Map<Integer, Integer> inorderMap, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight || inLeft > inRight)
            return null;
        // 找到当前位置
        int inRoot = inorderMap.get(preorder[preLeft]);
        // 找到左右子树节点数量
        int leftNum = inRoot - inLeft;
        int rightNum = inRight - inRoot;

        TreeNode tree = new TreeNode(preorder[preLeft]);
        tree.left = build(preorder, inorderMap, preLeft + 1, preLeft + leftNum, inLeft, inRoot - 1);
        tree.right = build(preorder, inorderMap, preLeft + leftNum + 1, preLeft + leftNum + rightNum, inRoot + 1, inRight);

        return tree;
    }

    /* 106. 从中序与后序遍历序列构造二叉树 */
    public TreeNode buildTree_(int[] inorder, int[] postorder) {
        // inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
        int len = inorder.length;
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build_(inorderMap, postorder, 0, len - 1, 0, len - 1);
    }

    private TreeNode build_(Map<Integer, Integer> inorderMap, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {
        if (postLeft > postRight || inLeft > inRight)
            return null;
        int inRoot = inorderMap.get(postorder[postRight]);
        int rightNum = inRight - inRoot;
        int leftNum = inRoot - inLeft;

        TreeNode root = new TreeNode(postorder[postRight]);
        root.right = build_(inorderMap, postorder, inRoot + 1, inRoot + rightNum, postRight - rightNum, postRight - 1);
        root.left = build_(inorderMap, postorder, inRoot - leftNum, inRoot - 1, postRight - rightNum - leftNum, postRight - rightNum - 1);
        return root;
    }


    /* 117. 填充每个节点的下一个右侧节点指针 II */
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "\n\tval=" + val +
                    ", \n\tleft=" + left +
                    ", \n\tright=" + right +
                    ", \n\tnext=" + next +
                    "\n}";
        }
    }

    public Node connect(Node root) {
        if (root == null)
            return null;
        Deque<Node> deque = new ArrayDeque<>();
        // 这个方法需要用到map记录层次信息，但这是可以被优化的，只需要在while中每次循环一次性拿出所有元素（即每一层的元素），再加入下一层元素
        Map<Node, Integer> map = new HashMap<>();
        deque.addLast(root);
        map.put(root, 1);
        while (!deque.isEmpty()) {
            Node nowNode = deque.pollFirst();
            int nowLevel = map.get(nowNode);
            // 如果此时deque有同一层的
            if (!deque.isEmpty() && map.containsKey(deque.peekFirst()) && map.get(deque.peekFirst()) == nowLevel)
                nowNode.next = deque.peekFirst();
            else
                nowNode.next = null;

            if (nowNode.left != null) {
                deque.addLast(nowNode.left);
                map.put(nowNode.left, nowLevel + 1);
            }
            if (nowNode.right != null) {
                deque.addLast(nowNode.right);
                map.put(nowNode.right, nowLevel + 1);
            }
        }
        return root;
    }

    public Node connect_noMap(Node root) {
        if (root == null)
            return null;
        // 这个方法还是用到了队列，有时间复杂度O(n)，要将其降为O(1)，需要在上一层就把下一层的next关系设置好，再遍历下一层
        Deque<Node> deque = new ArrayDeque<>();
        // while中每次循环一次性拿出所有元素（即每一层的元素），再加入下一层元素
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int nowDequeSize = deque.size();
            Node lastNode = null;
            for (int i = 0; i < nowDequeSize; i++) {
                Node nowNode = deque.pollFirst();
                if (i != 0)
                    lastNode.next = nowNode;
                if (nowNode.left != null) {
                    deque.addLast(nowNode.left);
                }
                if (nowNode.right != null) {
                    deque.addLast(nowNode.right);
                }
                lastNode = nowNode;
            }
        }
        return root;
    }

    public Node connect_O1(Node root) {
        if (root == null)
            return null;
        // 在上一层确定下一层的next关系，后遍历下一层，保证空间复杂度是O(1)
        Node nowStart = root;
        while (nowStart != null) {
            Node nextStart = null;
            Node preNode = null;
            for (Node nowNode = nowStart; nowNode != null; nowNode = nowNode.next) {
                if (nowNode.left != null) {
                    if (nextStart == null)
                        nextStart = nowNode.left;
                    if (preNode != null)
                        preNode.next = nowNode.left;
                    preNode = nowNode.left;
                }
                if (nowNode.right != null) {
                    if (nextStart == null)
                        nextStart = nowNode.right;
                    if (preNode != null)
                        preNode.next = nowNode.right;
                    preNode = nowNode.right;
                }
            }
            nowStart = nextStart;
        }

        return root;
    }

    /* 114. 二叉树展开为链表 */
    public void flatten(TreeNode root) {
        // 采用非原地算法，空间复杂度O(n)的算法
        List<TreeNode> list = new ArrayList<>();
        flatten_first_order(root, list);
        int len = list.size();
        for (int i = 0; i < len - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i + 1);
        }
    }

    private void flatten_first_order(TreeNode root, List<TreeNode> list) {
        if (root == null)
            return;
        list.add(root);
        flatten_first_order(root.left, list);
        flatten_first_order(root.right, list);
    }

    public void flatten_O1(TreeNode root) {
        // 原地算法 空间复杂度O(1)
        // 思想是，对于每个node，若有左子node，则将左子node的最右子node放在node右面
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                TreeNode next = node.left;
                TreeNode nextRightest = node.left;
                while (nextRightest.right != null)
                    nextRightest = nextRightest.right;
                nextRightest.right = node.right;
                node.right = next;
                node.left = null;
            }
            node = node.right;
        }
    }

    /* 112. 路径总和 */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) ||
                hasPathSum(root.right, targetSum - root.val);
    }

    /* 129. 求根节点到叶节点数字之和 */

    public int sumNumbers(TreeNode root) {
        return getSumNumbers(root, 0);
    }

    private int getSumNumbers(TreeNode root, int sum) {
        if (root == null)
            return 0;
        sum = 10 * sum + root.val;
        if (root.left == null && root.right == null)
            return sum;
        else
            return getSumNumbers(root.left, sum) + getSumNumbers(root.right, sum);
    }

    /* 173. 二叉搜索树迭代器 */
    static class BSTIterator {
        // 非常直观的方式，相当于提前算出来保存在list中，但可能效率不高
        List<Integer> list;
        int pointer;

        public BSTIterator(TreeNode root) {
            list = new ArrayList<>();
            pointer = 0;
            // 中序遍历
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while (!stack.isEmpty() || node != null) {
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                node = stack.pop();
                list.add(node.val);
                node = node.right;
            }
        }

        public int next() {
            if (pointer == list.size())
                return -1;
            int ans = list.get(pointer);
            pointer++;
            return ans;
        }

        public boolean hasNext() {
            return pointer != list.size();
        }
    }

    static class BSTIterator_ {
        // 既然我们之前用到了栈，那不就可以实时获取下一个吗
        Stack<TreeNode> stack;
        TreeNode node;

        public BSTIterator_(TreeNode root) {
            stack = new Stack<>();
            node = root;
        }

        public int next() {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            int next = node.val;
            node = node.right;
            return next;
        }

        public boolean hasNext() {
            return !stack.isEmpty() || node != null;
        }
    }

    /* 222. 完全二叉树的节点个数 */
    public int countNodes(TreeNode root) {
        // 最简单的方式是，遍历一遍，但题目是完全二叉树，应该可以利用其性质优化
        if (root == null)
            return 0;
        if (root.left == null)
            return 1;
        /*
        我的思路：
            1. 先一直往左遍历，确定层数h。
            2. 从左到右(从右到左)遍历所有h-1层的节点，确定最后一层有多少个
            3. h-1层的所有+最后一层计算得到答案
        问题：
            最差、平均情况下时间复杂度为O(n)，并没有优化多少
        */
        TreeNode node = root;
        int ans;
        int h = 1;
        while (node.left != null) {
            node = node.left;
            h++;
        }
        ans = (int) (Math.pow(2, h - 1) - 1);

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> stack_h = new Stack<>();
        node = root;
        int nowH = 1;
        int leaf = 0;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                stack_h.push(nowH);
                node = node.left;
                nowH++;
            }
            node = stack.pop();
            nowH = stack_h.pop();

            if (nowH == h - 1) {
                if (node.left != null)
                    leaf++;
                else
                    break;
                if (node.right != null)
                    leaf++;
                else
                    break;
            }

            node = node.right;
            nowH++;
        }

        return ans + leaf;
    }

    public int countNodes_(TreeNode root) {
        // 利用二分查找
        if (root == null)
            return 0;
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }
        int low = (int) Math.pow(2, level);
        int high = (int) Math.pow(2, level + 1) - 1;
        while (low < high) {
            // 这里括号里加一，表示选中间偏右的节点
            int mid = (high + low + 1) / 2;
            if (leafExist(root, level, mid))
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }

    public boolean leafExist(TreeNode root, int level, int k) {
        String k_binary = Integer.toBinaryString(k);
        TreeNode node = root;
        for (int i = 1; i < k_binary.length(); i++) {
            if (node == null)
                return false;
            if (k_binary.charAt(i) == '0') {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return true;
    }

    /* 236. 二叉树的最近公共祖先 */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null)
            return right;
        if (right == null)
            return left;

        return root;
    }


    /* 调试 */
    public static void main(String[] args) {
        Classic150_binaryTree binaryTree = new Classic150_binaryTree();
        TreeNode l = new TreeNode(2);
        TreeNode r = new TreeNode(3);
        TreeNode root = new TreeNode(1, l, r);
        int n = binaryTree.sumNumbers(root);
        System.out.println(n);
    }
}
